/**
*
* @see AnimationSort
* @see com.uow.algdemo.animation.AnimationSort
*
* @version 0.1
* @author Zaixiang Wu
*/
package com.uow.algdemo.algorithms;

import java.util.ArrayList;
import java.util.List;

import android.util.Log;

/**
 * This class will receive a set of numbers and sort these data, then generate animation steps.
 */
public class Sort
{
    /**
     * This is the array of integers waiting for sort.
     */
	private int[] array;
    /**
     * This array contains steps of sorting animation.
     */
	private List<int[][]> steps = new ArrayList<int[][]>();
    /**
     * This is the length of unsorted and sorted array.
     */
	private int length;
	/**
	 * @param newArray The unsorted array from input.
	 */
	public Sort(int[] newArray)
	{
		array = new int[newArray.length];
		length = array.length;
		for(int i = 0; i < length; i++)
		{
			array[i] = newArray[i];
		}
	}
	/**
	 * @return The steps of sorting movement.
	 */
	public List<int[][]> getSteps()
	{
		return steps;
	}
    /**
     * This method records steps for compare two integers.
     * @param first First integer for comparing.
     * @param second Second integer for comparing.
     */
	private void compare(int first, int second)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 0;
		tmp[1][0] = first;
		tmp[2][0] = second;
		Log.v("Sort", first + "-" + second);
		steps.add(tmp);
	}
    /**
     * This method records steps for swap two integers.
     * @param first First integer for comparing.
     * @param second Second integer for comparing.
     */
	private void swap(int first, int second)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 1;
		tmp[1][0] = first;
		tmp[2][0] = second;
		steps.add(tmp);
	}
    /**
     * This method generate step for move up an integer.
     * @param index Index of integer for move up.
     */
	private void moveup(int index)
	{
		int[][] tmp = new int[2][1];
		tmp[0][0] = 2;
		tmp[1][0] = index;
		Log.v("Insert", "Move up " + index);
		steps.add(tmp);
	}
    /**
     * This method generate step for move an integer to next position.
     * @param index Index of integer for moving.
     */
	private void movenext(int index)
	{
		int[][] tmp = new int[2][1];
		tmp[0][0] = 3;
		tmp[1][0] = index;
		Log.v("Insert", "Move next " + index);
		steps.add(tmp);
	}
    /**
     * This method generate step for move down an integer to empty position.
     * @param indexSource Index of integer before moving.
     * @param indexTarget Index of integer after moving.
     */
	private void movedown(int indexSource, int indexTarget)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 4;
		tmp[1][0] = indexSource;
		tmp[2][0] = indexTarget;
		Log.v("Insert", "Move down " + indexSource);
		steps.add(tmp);
	}
	/**
     * This method sorts array use algorithm of bubble sort, then records steps to list of steps.
     */
	public void sortBubble()
	{
		int[] a = new int[length];
		a = array;
		int n = length;
		int i,j,t=0;
		for(i = 0; i < n; i++)
		{
			for(j = 1; j < (n-i); j++)
			{
				compare((j-1),j);
				if(a[j-1] > a[j])
				{
					swap((j-1),j);
					t = a[j-1];
					a[j-1] = a[j];
					a[j] = t;
				}
			}
		}
	}
    /**
     * This method sorts array use algorithm of insertion sort, then records steps to list of steps.
     */
	public void sortInsertion()
	{
		int[] a = new int[length];
		a = array;
		int n = length;
		
		
		for (int i = 1; i < n; i++)
		{
			int j = i;
			int tmp = a[i]; // wait for inserting data
			moveup(i);
			while (j > 0)
			{
				compare(j - 1, i);
				if(a[j - 1] > tmp)
				{
					a[j] = a[j - 1];
					movenext(j-1);
					j--;
				}
				else
				{
					break;
				}
			}
			a[j] = tmp;
			movedown(i,j);
		}
	}
    /**
     * This method sorts array use algorithm of selection sort, then records steps to list of steps.
     */
	public void sortSelection()
	{
		int[] a = new int[length];
		a = array;
		int n = length;
		
		for(int i = 0;i < n;i++)
		{
			int pos = i;
			for(int j = i+1;j < n;j++)
			{
				compare(pos, j);
				if (a[pos] > a[j])
				{
					pos = j;
				}
			}
			int tem;
			if(pos != i)
			{
				swap(pos,i);
				tem = a[pos];
				a[pos] = a[i];
				a[i] = tem;
			}
		}
	}
    /**
     * This method sorts array use algorithm of quick sort, then records steps to list of steps.
     */
	public void sortQuick()
	{
		int[] a = new int[length];
		a = array;
		quick(a, 0, length - 1);
	}
	/**
     * This method is main function for quick sorting.
     * @param a Array for sorting.
     * @param low Low position.
     * @param high High position.
     */
	public void quick(int[] a, int low, int high)
	{
		int i = low;
		int j = high;
		int key = a[low];
		
		while (i< j)
		{
			while(i < j && a[j] >= key)
			{
				j--;//scan from right,if right is bigger, pass
		    }
			compare(i,j);
		    if(i<j)
		    {  //else swap position
				swap(i,j);
				a[i] = a[j];
				i ++; //move point at left by 1
			}
			while(i< j && a[i]< key)
			{ //  scan from left, if left is smaller, pass.
				i++ ;
	    	}
			compare(i,j);
	    	if(i< j)
	    	{
	    		swap(j,i);
	    		a[j] = a[i];
	    		j--;
	    	}
	    }

		a[i] = key;//change key
		if(i > low) quick(a, low, i-1);
		if(i < high) quick(a, i+1, high);
	}
    /**
     * This method sorts array use algorithm of shell sort, then records steps to list of steps.
     */
	public void sortShell()
	{
		int[] a = new int[length];
		a = array;
		int n = length;
		
		int d, i, j, temp;
		
		for(d = n/2;d >= 1;d = d/2)
		{
			for(i = d; i < n;i++)
			{	
				temp = a[i];
				j = i - d;
				compare(j,i);
				int count=0;
				while((j >= 0) && (a[j] > temp))
				{
					if(count >0)
						compare(j+d,j);
					swap((j+d),j);
					a[j + d] = a[j];
					j = j-d;
					count++;
				}
				a[j + d]=temp;
			}
		}
	}
}
